home *** CD-ROM | disk | FTP | other *** search
/ Qoole for Quake / Qoole for Quake (USA) / Qoole for Quake (USA).bin / Tutorial / HTML / QUBE.ZIP / SRC / PORTALS.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-11-05  |  12.2 KB  |  586 lines
  1.  
  2. #include "bsp5.h"
  3.  
  4.  
  5. node_t    outside_node;        /* portals outside the world face this */
  6.  
  7. /*============================================================================= */
  8.  
  9. /*
  10. =============
  11. AddPortalToNodes
  12. =============
  13. */
  14. void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
  15. {
  16.     if (p->nodes[0] || p->nodes[1])
  17.         Error ("AddPortalToNode: allready included");
  18.  
  19.     p->nodes[0] = front;
  20.     p->next[0] = front->portals;
  21.     front->portals = p;
  22.     
  23.     p->nodes[1] = back;
  24.     p->next[1] = back->portals;
  25.     back->portals = p;
  26. }
  27.  
  28.  
  29. /*
  30. =============
  31. RemovePortalFromNode
  32. =============
  33. */
  34. void RemovePortalFromNode (portal_t *portal, node_t *l)
  35. {
  36.     portal_t    **pp, *t;
  37.     
  38. /* remove reference to the current portal */
  39.     pp = &l->portals;
  40.     while (1)
  41.     {
  42.         t = *pp;
  43.         if (!t)
  44.             Error ("RemovePortalFromNode: portal not in leaf");    
  45.  
  46.         if ( t == portal )
  47.             break;
  48.  
  49.         if (t->nodes[0] == l)
  50.             pp = &t->next[0];
  51.         else if (t->nodes[1] == l)
  52.             pp = &t->next[1];
  53.         else
  54.             Error ("RemovePortalFromNode: portal not bounding leaf");
  55.     }
  56.     
  57.     if (portal->nodes[0] == l)
  58.     {
  59.         *pp = portal->next[0];
  60.         portal->nodes[0] = NULL;
  61.     }
  62.     else if (portal->nodes[1] == l)
  63.     {
  64.         *pp = portal->next[1];    
  65.         portal->nodes[1] = NULL;
  66.     }
  67. }
  68.  
  69. /*============================================================================ */
  70.  
  71. void PrintPortal (portal_t *p)
  72. {
  73.     int            i;
  74.     winding_t    *w;
  75.     
  76.     w = p->winding;
  77.     for (i=0 ; i<w->numpoints ; i++)
  78.         printf ("(%5.0f,%5.0f,%5.0f)\n",w->points[i][0]
  79.         , w->points[i][1], w->points[i][2]);
  80. }
  81.  
  82. /*
  83. ================
  84. MakeHeadnodePortals
  85.  
  86. The created portals will face the global outside_node
  87. ================
  88. */
  89. void MakeHeadnodePortals (node_t *node)
  90. {
  91.     vec3_t        bounds[2];
  92.     int            i, j, n;
  93.     portal_t    *p, *portals[6];
  94.     plane_t        bplanes[6], *pl;
  95.     int            side;
  96.     
  97.     Draw_ClearWindow ();
  98.     
  99. /* pad with some space so there will never be null volume leafs */
  100.     for (i=0 ; i<3 ; i++)
  101.     {
  102.         bounds[0][i] = brushset->mins[i] - SIDESPACE;
  103.         bounds[1][i] = brushset->maxs[i] + SIDESPACE;
  104.     }
  105.     
  106.     outside_node.contents = CONTENTS_SOLID;
  107.     outside_node.portals = NULL;
  108.  
  109.     for (i=0 ; i<3 ; i++)
  110.         for (j=0 ; j<2 ; j++)
  111.         {
  112.             n = j*3 + i;
  113.  
  114.             p = AllocPortal ();
  115.             portals[n] = p;
  116.             
  117.             pl = &bplanes[n];
  118.             memset (pl, 0, sizeof(*pl));
  119.             if (j)
  120.             {
  121.                 pl->normal[i] = -1;
  122.                 pl->dist = -bounds[j][i];
  123.             }
  124.             else
  125.             {
  126.                 pl->normal[i] = 1;
  127.                 pl->dist = bounds[j][i];
  128.             }
  129.             p->planenum = FindPlane (pl, &side);
  130.     
  131.             p->winding = BaseWindingForPlane (pl);
  132.             if (side)
  133.                 AddPortalToNodes (p, &outside_node, node);
  134.             else
  135.                 AddPortalToNodes (p, node, &outside_node);
  136.         }
  137.         
  138. /* clip the basewindings by all the other planes */
  139.     for (i=0 ; i<6 ; i++)
  140.     {
  141.         for (j=0 ; j<6 ; j++)
  142.         {
  143.             if (j == i)
  144.                 continue;
  145.             portals[i]->winding = ClipWinding (portals[i]->winding, &bplanes[j], true);
  146.         }
  147.     }
  148. }
  149.  
  150. /*============================================================================ */
  151.  
  152. void CheckWindingInNode (winding_t *w, node_t *node)
  153. {
  154.     int        i, j;
  155.     
  156.     for (i=0 ; i<w->numpoints ; i++)
  157.     {
  158.         for (j=0 ; j<3 ; j++)
  159.             if (w->points[i][j] < node->mins[j] - 1
  160.             || w->points[i][j] > node->maxs[j] + 1)
  161.             {
  162.                 ShowWarningEntry ("CheckWindingInNode: outside");
  163.                 sleep(1);
  164.                                 return;
  165.             }
  166.     }
  167. }
  168.  
  169. void CheckWindingArea (winding_t *w)
  170. {
  171.     int        i;
  172.     float    total, add;
  173.     vec3_t    v1, v2, cross;
  174.     
  175.     total = 0;
  176.     for (i=1 ; i<w->numpoints ; i++)
  177.     {
  178.         VectorSubtract (w->points[i], w->points[0], v1);
  179.         VectorSubtract (w->points[i+1], w->points[0], v2);
  180.         CrossProduct (v1, v2, cross);
  181.         add = VectorLength (cross);
  182.         total += add*0.5;
  183.     }
  184.     if (total < 16) {
  185.         ShowWarningEntry ("Winding area %f", total);
  186.         sleep(1);
  187.         }
  188. }
  189.  
  190.  
  191. void PlaneFromWinding (winding_t *w, plane_t *plane)
  192. {
  193.     vec3_t        v1, v2;
  194.  
  195. /* calc plane */
  196.     VectorSubtract (w->points[2], w->points[1], v1);
  197.     VectorSubtract (w->points[0], w->points[1], v2);
  198.     CrossProduct (v2, v1, plane->normal);
  199.     VectorNormalize (plane->normal);
  200.     plane->dist = DotProduct (w->points[0], plane->normal);
  201. }
  202.  
  203. void CheckLeafPortalConsistancy (node_t *node)
  204. {
  205.     int            side, side2;
  206.     portal_t    *p, *p2;
  207.     plane_t        plane, plane2;
  208.     int            i;
  209.     winding_t    *w;
  210.     float        dist;
  211.  
  212.     side = side2 = 0;        /* quiet compiler warning */
  213.  
  214.     for (p = node->portals ; p ; p = p->next[side])    
  215.     {
  216.         if (p->nodes[0] == node)
  217.             side = 0;
  218.         else if (p->nodes[1] == node)
  219.             side = 1;
  220.         else
  221.             Error ("CutNodePortals_r: mislinked portal");
  222.         CheckWindingInNode (p->winding, node);
  223.         CheckWindingArea (p->winding);
  224.  
  225.     /* check that the side orders are correct */
  226.         plane = planes[p->planenum];
  227.          PlaneFromWinding (p->winding, &plane2);
  228.         
  229.         for (p2 = node->portals ; p2 ; p2 = p2->next[side2])    
  230.         {
  231.             if (p2->nodes[0] == node)
  232.                 side2 = 0;
  233.             else if (p2->nodes[1] == node)
  234.                 side2 = 1;
  235.             else
  236.                 Error ("CutNodePortals_r: mislinked portal");
  237.             w = p2->winding;
  238.             for (i=0 ; i<w->numpoints ; i++)
  239.             {
  240.                 dist = DotProduct (w->points[i], plane.normal) - plane.dist;
  241.                 if ( (side == 0 && dist < -1) || (side == 1 && dist > 1) )
  242.                 {
  243.                     ShowWarningEntry("Portal siding direction is wrong.");
  244.                     sleep(1);
  245.                                         return;
  246.                 }
  247.             }
  248.             
  249.         }
  250.     }
  251. }
  252.  
  253.  
  254. /*
  255. ================
  256. CutNodePortals_r
  257.  
  258. ================
  259. */
  260. void CutNodePortals_r (node_t *node)
  261. {
  262.     plane_t     *plane, clipplane;
  263.     node_t        *f, *b, *other_node;
  264.     portal_t    *p, *new_portal, *next_portal;
  265.     winding_t    *w, *frontwinding, *backwinding;
  266.     int            side;
  267.  
  268. /*    CheckLeafPortalConsistancy (node); */
  269.  
  270. /* */
  271. /* seperate the portals on node into it's children     */
  272. /* */
  273.     if (node->contents)
  274.     {
  275.         return;            /* at a leaf, no more dividing */
  276.     }
  277.  
  278.     plane = &planes[node->planenum];
  279.  
  280.     f = node->children[0];
  281.     b = node->children[1];
  282.  
  283. /* */
  284. /* create the new portal by taking the full plane winding for the cutting plane */
  285. /* and clipping it by all of the planes from the other portals */
  286. /* */
  287.     new_portal = AllocPortal ();
  288.     new_portal->planenum = node->planenum;
  289.     
  290.     w = BaseWindingForPlane (&planes[node->planenum]);
  291.     side = 0;    /* shut up compiler warning */
  292.     for (p = node->portals ; p ; p = p->next[side])    
  293.     {
  294.         clipplane = planes[p->planenum];
  295.         if (p->nodes[0] == node)
  296.             side = 0;
  297.         else if (p->nodes[1] == node)
  298.         {
  299.             clipplane.dist = -clipplane.dist;
  300.             VectorSubtract (vec3_origin, clipplane.normal, clipplane.normal);
  301.             side = 1;
  302.         }
  303.         else
  304.             Error ("CutNodePortals_r: mislinked portal");
  305.  
  306.         w = ClipWinding (w, &clipplane, true);
  307.         if (!w)
  308.         {
  309.             ShowWarningEntry("New portal was clipped away.  Part");
  310.             ShowWarningEntry("of the map may have been removed.");
  311.             sleep(1);
  312.                         break;
  313.         }
  314.     }
  315.     
  316.     if (w)
  317.     {
  318.     /* if the plane was not clipped on all sides, there was an error */
  319.         new_portal->winding = w;    
  320.         AddPortalToNodes (new_portal, f, b);
  321.     }
  322.  
  323. /* */
  324. /* partition the portals */
  325. /* */
  326.     for (p = node->portals ; p ; p = next_portal)    
  327.     {
  328.         if (p->nodes[0] == node)
  329.             side = 0;
  330.         else if (p->nodes[1] == node)
  331.             side = 1;
  332.         else
  333.             Error ("CutNodePortals_r: mislinked portal");
  334.         next_portal = p->next[side];
  335.  
  336.         other_node = p->nodes[!side];
  337.         RemovePortalFromNode (p, p->nodes[0]);
  338.         RemovePortalFromNode (p, p->nodes[1]);
  339.  
  340. /* */
  341. /* cut the portal into two portals, one on each side of the cut plane */
  342. /* */
  343.         DivideWinding (p->winding, plane, &frontwinding, &backwinding);
  344.         
  345.         if (!frontwinding)
  346.         {
  347.             if (side == 0)
  348.                 AddPortalToNodes (p, b, other_node);
  349.             else
  350.                 AddPortalToNodes (p, other_node, b);
  351.             continue;
  352.         }
  353.         if (!backwinding)
  354.         {
  355.             if (side == 0)
  356.                 AddPortalToNodes (p, f, other_node);
  357.             else
  358.                 AddPortalToNodes (p, other_node, f);
  359.             continue;
  360.         }
  361.         
  362.     /* the winding is split */
  363.         new_portal = AllocPortal ();
  364.         *new_portal = *p;
  365.         new_portal->winding = backwinding;
  366.         FreeWinding (p->winding);
  367.         p->winding = frontwinding;
  368.  
  369.         if (side == 0)
  370.         {
  371.             AddPortalToNodes (p, f, other_node);
  372.             AddPortalToNodes (new_portal, b, other_node);
  373.         }
  374.         else
  375.         {
  376.             AddPortalToNodes (p, other_node, f);
  377.             AddPortalToNodes (new_portal, other_node, b);
  378.         }
  379.     }
  380.     
  381. DrawLeaf (f,1);
  382. DrawLeaf (b,2);    
  383.  
  384.     CutNodePortals_r (f);    
  385.     CutNodePortals_r (b);    
  386.  
  387. }
  388.  
  389.  
  390. /*
  391. ==================
  392. PortalizeWorld
  393.  
  394. Builds the exact polyhedrons for the nodes and leafs
  395. ==================
  396. */
  397. void PortalizeWorld (node_t *headnode)
  398. {
  399.     ShowStatusEntry("Portalizing.");
  400.     ShowTempEntry("Building exact polyhedrons for");
  401.     ShowTempEntry("nodes and leafs.");
  402.  
  403.     MakeHeadnodePortals (headnode);
  404.     CutNodePortals_r (headnode);    
  405. }
  406.  
  407.  
  408. /*
  409. ==================
  410. FreeAllPortals
  411.  
  412. ==================
  413. */
  414. void FreeAllPortals (node_t *node)
  415. {
  416.     portal_t    *p, *nextp;
  417.     
  418.     if (!node->contents)
  419.     {
  420.         FreeAllPortals (node->children[0]);
  421.         FreeAllPortals (node->children[1]);
  422.     }
  423.     
  424.     for (p=node->portals ; p ; p=nextp)
  425.     {
  426.         if (p->nodes[0] == node)
  427.             nextp = p->next[0];
  428.         else
  429.             nextp = p->next[1];
  430.         RemovePortalFromNode (p, p->nodes[0]);
  431.         RemovePortalFromNode (p, p->nodes[1]);
  432.         FreeWinding (p->winding);
  433.         FreePortal (p);
  434.     }
  435. }
  436.  
  437. /*
  438. ==============================================================================
  439.  
  440. PORTAL FILE GENERATION
  441.  
  442. ==============================================================================
  443. */
  444.  
  445. #define    PORTALFILE    "PRT1"
  446.  
  447. FILE    *pf;
  448. int        num_visleafs;                /* leafs the player can be in */
  449. int        num_visportals;
  450.  
  451. void WriteFloat (FILE *f, double v)
  452. {
  453.     if ( fabs(v - Q_rint(v)) < 0.001 )
  454.         fprintf (f,"%i ",(int)Q_rint(v));
  455.     else
  456.         fprintf (f,"%f ",v);
  457. }
  458.  
  459. void WritePortalFile_r (node_t *node)
  460. {
  461.     int        i;    
  462.     portal_t    *p;
  463.     winding_t    *w;
  464.     plane_t        *pl, plane2;
  465.  
  466.     if (!node->contents)
  467.     {
  468.         WritePortalFile_r (node->children[0]);
  469.         WritePortalFile_r (node->children[1]);
  470.         return;
  471.     }
  472.     
  473.     if (node->contents == CONTENTS_SOLID)
  474.         return;
  475.  
  476.     for (p = node->portals ; p ; )
  477.     {
  478.         w = p->winding;
  479.         if (w && p->nodes[0] == node
  480.         && p->nodes[0]->contents == p->nodes[1]->contents)
  481.         {
  482.         /* write out to the file */
  483.         
  484.         /* sometimes planes get turned around when they are very near */
  485.         /* the changeover point between different axis.  interpret the */
  486.         /* plane the same way vis will, and flip the side orders if needed */
  487.             pl = &planes[p->planenum];
  488.             PlaneFromWinding (w, &plane2);
  489.             if ( DotProduct (pl->normal, plane2.normal) < 0.99 )
  490.             {    /* backwards... */
  491.                 fprintf (pf,"%i %i %i ",w->numpoints, p->nodes[1]->visleafnum, p->nodes[0]->visleafnum);
  492.             }
  493.             else
  494.                 fprintf (pf,"%i %i %i ",w->numpoints, p->nodes[0]->visleafnum, p->nodes[1]->visleafnum);
  495.             for (i=0 ; i<w->numpoints ; i++)
  496.             {
  497.                 fprintf (pf,"(");
  498.                 WriteFloat (pf, w->points[i][0]);
  499.                 WriteFloat (pf, w->points[i][1]);
  500.                 WriteFloat (pf, w->points[i][2]);
  501.                 fprintf (pf,") ");
  502.             }
  503.             fprintf (pf,"\n");
  504.         }
  505.         
  506.         if (p->nodes[0] == node)
  507.             p = p->next[0];
  508.         else
  509.             p = p->next[1];
  510.     }
  511.  
  512. }
  513.     
  514. /*
  515. ================
  516. NumberLeafs_r
  517. ================
  518. */
  519. void NumberLeafs_r (node_t *node)
  520. {
  521.     portal_t    *p;
  522.  
  523.     if (!node->contents)
  524.     {    /* decision node */
  525.         node->visleafnum = -99;
  526.         NumberLeafs_r (node->children[0]);
  527.         NumberLeafs_r (node->children[1]);
  528.         return;
  529.     }
  530.     
  531.     Draw_ClearWindow ();
  532.     DrawLeaf (node, 1);
  533.     
  534.     if (node->contents == CONTENTS_SOLID)
  535.     {    /* solid block, viewpoint never inside */
  536.         node->visleafnum = -1;
  537.         return;
  538.     }
  539.  
  540.     node->visleafnum = num_visleafs++;
  541.     
  542.     for (p = node->portals ; p ; )
  543.     {
  544.         if (p->nodes[0] == node)        /* only write out from first leaf */
  545.         {
  546.             if (p->nodes[0]->contents == p->nodes[1]->contents)
  547.                 num_visportals++;
  548.             p = p->next[0];
  549.         }
  550.         else
  551.             p = p->next[1];        
  552.     }
  553.  
  554. }
  555.  
  556.  
  557. /*
  558. ================
  559. WritePortalfile
  560. ================
  561. */
  562. void WritePortalfile (node_t *headnode)
  563. {
  564. /* set the visleafnum field in every leaf and count the total number of portals */
  565.     num_visleafs = 0;
  566.     num_visportals = 0;
  567.     NumberLeafs_r (headnode);
  568.     
  569. /* write the file */
  570.     ShowTempEntry ("Writing portal file for Vis:");
  571.     ShowTempEntry ("  %s", portfilename);
  572.     pf = fopen (portfilename, "w");
  573.     if (!pf)
  574.         Error ("Error opening %s", portfilename);
  575.         
  576.     fprintf (pf, "%s\n", PORTALFILE);
  577.     fprintf (pf, "%i\n", num_visleafs);
  578.     fprintf (pf, "%i\n", num_visportals);
  579.     
  580.     WritePortalFile_r (headnode);
  581.     
  582.     fclose (pf);
  583. }
  584.  
  585.  
  586.